package com.ycz.algorithm.utils.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author yancz
 * @ClassName TreeUtil
 * @description: TODO
 * @date 2024-12-18 16:34:08
 * @version: 1.0
 */
public class TreeUtil {

    public static void main(String[] args) {
        TreeNode root = TreeUtil.initTree();
        List<Integer> list = TreeUtil.levelOrder(root);
        System.out.println("层序遍历顺序：");
        printCommon(list);
        list.clear();
        TreeUtil.preOrder(root, list);
        System.out.println("先序遍历顺序：");
        printCommon(list);
        list.clear();
        TreeUtil.midOrder(root, list);
        System.out.println("中序遍历顺序：");
        printCommon(list);
        list.clear();
        TreeUtil.nextOrder(root, list);
        System.out.println("后序遍历顺序：");
        printCommon(list);
    }

    /*
     * @author yancz
     * @description 后序遍历，访问顺序：左 -> 右 -> 根
     * @date 2024/12/18 17:26
     * @param root
     * @param list
     **/
    public static void nextOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        nextOrder(root.left, list);
        nextOrder(root.right, list);
        list.add(root.val);
    }

    /*
     * @author yancz
     * @description 中序遍历，访问顺序：左 -> 根 -> 右
     * @date 2024/12/18 17:07
     * @param root
     * @param list
     **/
    public static void midOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        midOrder(root.left, list);
        list.add(root.val);
        midOrder(root.right, list);
    }

    /*
     * @author yancz
     * @description 先序遍历，访问顺序：根 -> 左 -> 右
     * @date 2024/12/18 16:56
     * @param root
     * @param list
     **/
    public static void preOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }

    /*
     * @author yancz
     * @description 树的层序遍历， 属于广度优先搜索
     * @date 2024/12/18 16:44
     * @param root
     * @return List<Integer>
     **/
    public static List<Integer> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) { // 队列不为空时，遍历
            TreeNode node = queue.poll(); // 出队
            list.add(node.val);
            if (node.left != null) {
                queue.offer(node.left); // 左节点入队列
            }
            if (node.right != null) {
                queue.offer(node.right); // 右节点入队列
            }
        }
        return list;
    }

    /*
     * @author yancz
     * @description 树节点初始化
     * @date 2024/12/18 16:39
     * @return TreeNode 返回根结点
     **/
    private static TreeNode initTree() {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t2.left = t4;
        t2.right = t5;
        TreeNode t3 = new TreeNode(3);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        t3.left = t6;
        t3.right = t7;
        t1.left = t2;
        t1.right = t3;
        return t1;
    }

    // 树输出节点元素值
    private static void printCommon(List<Integer> list) {
        for (int i : list) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }

}
